//============================================================================
// Name        : worklist.c
// Author      : Yugi
// Version     : 1.0
// Description : 
//============================================================================

#include "worklist.h"

/* 
* Generate a worklist.
* 
* RETURN:	new worklist
* NOTES:	Return value should be freed by user
*/
PWORKLIST wl_new(){
	PWORKLIST pList = (PWORKLIST) malloc(sizeof(WORKLIST));

	pList->head = NULL;
	pList->tail = NULL;
	pList->size = 0;

	return pList;
}

/* 
* Make a copy of the input worklist
* 
* REQUIRE:	src not NULL
* RETURN:	clone of src
* NOTES:	Return value should be freed by user
*/
PWORKLIST wl_clone(PWORKLIST src){
	PWORKLIST pList = wl_new();
	PNODE pNode = src->head;

	while (pNode){
		wl_append(pList, pNode->value);
		pNode = pNode->next;
	}

	return pList;
}

/* 
* Merge worklists
*
* REQUIRE:	pList1, pList2 not NULL
* NOTES:	Return value should be freed by user
*/
PWORKLIST wl_merge(PWORKLIST pList1, PWORKLIST pList2){
	PWORKLIST pList = wl_new();
	PNODE pNode;
	
	pNode = pList1->head;

	while (pNode){
		wl_append(pList, pNode->value);
		pNode = pNode->next;
	}
	
	pNode = pList2->head;

	while (pNode){
		wl_gen(pList, pNode->value);
		pNode = pNode->next;
	}

	return pList;
}

/* 
* Test if pList1 contains pList2
*
* REQUIRE:	pList1, pList2 not NULL
* RETURN:	true if pList1 contains pList2
* NOTES:	Return value should be freed by user
*/
bool wl_subset(PWORKLIST pList1, PWORKLIST pList2){
	PNODE pNode;
	
	pNode = pList2->head;

	while (pNode){
		if (!wl_contain(pList1, pNode->value))
			return false;

		pNode = pNode->next;
	}

	return true;
}

/* 
* Free the input worklist
*
* REQUIRE:	src not NULL
*/
void wl_delete(PWORKLIST pList){
	PNODE pNode = pList->head;

	while (pNode){
		pList->head = pNode->next;
		free(pNode);
		pNode = pList->head;
	}

	free(pList);
	pList = NULL;
}

/* 
* Add a node with 'value' to the end of 'pList'.
* 
* REQUIRE:	pList not NULL
* MODIFY:	pList
*/
void wl_append(PWORKLIST pList, opnd_t value){
	PNODE pNode = (PNODE) malloc(sizeof(NODE));

	/* Initial a node */
	pNode->value = value;
	pNode->prev = NULL;
	pNode->next = NULL;

	/* Relocate pointers */
	if (pList->tail == NULL){
		pList->head = pList->tail = pNode;
	}else{
		pNode->prev = pList->tail;
		pList->tail->next = pNode;
		pList->tail = pNode;
	}

	pList->size++;
}

/* 
* Add a node with 'value' to the front of 'pList'.
* 
* REQUIRE:	pList not NULL
* MODIFY:	pList
*/
void wl_prepend(PWORKLIST pList, opnd_t value){
	PNODE pNode = (PNODE) malloc(sizeof(NODE));

	/* Initial a node */
	pNode->value = value;
	pNode->prev = NULL;
	pNode->next = NULL;

	/* Relocate pointers */
	if (pList->head == NULL){
		pList->head = pList->tail = pNode;
	}else{
		pNode->next = pList->head;
		pList->head->prev = pNode;
		pList->head = pNode;
	}

	pList->size++;
}

/* 
* Test if 'pList' contains value.
*
* REQUIRE:	pList not NULL
* RETURN:	true if 'pList' contains value, false otherwise
* NOTES:	Only registers and base-disp operands will be tested
*/
bool wl_contain(PWORKLIST pList, opnd_t value){
	PNODE itr = pList->head;

	if (!(opnd_is_reg(value) || opnd_is_base_disp(value)))
		return false;

	/* Iterate through 'pList' */
	while (itr){
		if (opnd_same(itr->value, value))
			return true;

		itr = itr->next;
	}

	/* Could not find any node that meets 'value' */
	return false;
}

/* 
* Remove node with 'value' from 'pList'. 
*
* REQUIRE:	pList not NULL
* RETURN:	true if 'pList' contains value, false otherwise
* MODIFY:	pList
* NOTES:	Only registers and base-disp operands will be removed.
*/
bool wl_kill(PWORKLIST pList, opnd_t value){
	PNODE itr = pList->head;

	if (!(opnd_is_reg(value) || opnd_is_base_disp(value)))
		return false;

	/* Iterate through 'pList' */
	while (itr){
		if (opnd_same(itr->value, value))
			break;

		itr = itr->next;
	}

	/* Could not find any node that meets 'value' */
	if (!itr)
		return false;

	/* Relocate prev->next */
	if (itr == pList->head)
		pList->head = itr->next;
	else
		itr->prev->next = itr->next;

	/* Relocate next->prev */
	if (itr == pList->tail)
		pList->tail = itr->prev;
	else
		itr->next->prev = itr->prev;

	/* Free the node */
	free(itr);

	pList->size--;

	if (pList->size == 0)
		pList->head = pList->tail = NULL;

	return true;
}

/* 
* Insert node  with 'value' into 'pList'
*
* REQUIRE:	pList not NULL
* RETURN:	true if 'pList' does not contain value, false otherwise
* MODIFY:	pList
* NOTES:	Only registers and base-disp operands will be added.
*/
bool wl_gen(PWORKLIST pList, opnd_t value){
	PNODE itr = pList->head;

	if (!(opnd_is_reg(value) || opnd_is_base_disp(value)))
		return false;

	/* Iterate through 'pList' */
	while (itr){
		if (opnd_same(itr->value, value))
			break;

		itr = itr->next;
	}

	/* Already contains node that meets 'value' */
	if (itr != NULL)
		return false;

	wl_append(pList, value);

	return true;
}

/* Print a worklist using <opnd_disassemble> */
void wl_print(void *drcontext, PWORKLIST pList, file_t outfile){
	PNODE itr = pList->head;
	dr_fprintf(outfile, "----Worklist----\n");

	/* Iterate through 'pList' */
	while (itr){
		opnd_disassemble(drcontext, itr->value, outfile);
		dr_fprintf(outfile, "\n");
		itr = itr->next;
	}
}